Communication networks have experienced an enormous rise in volume of data traffic over the past decade. This trend is expected to continue due to a growing popularity of the Internet and an emergence of new applications that utilize such networks. As a result, proper utilization of network resources, such as bandwidth, has become ever so important.
In addition to the rising traffic volumes, there has also been an evolution in the underlying networks. From physical layer and up, network topologies have become more mesh-like, allowing multiple diverse paths between source and destination nodes. A high degree of connectedness in a network allows networking equipment to share traffic load (“load sharing”) across multiple diverse paths, and hence, better network utilization. Theoretically, such load sharing can be achieved through congestion-aware routing algorithms and/or multi-path routing.
In addition to multipath routing, the networking equipment can be configured to statistically distribute the data traffic over a set, N, of its forwarding interfaces, ports, or bins (collectively “interfaces”) to achieve a greater aggregate transmission bandwidth than one of such forwarding interfaces. This practice is known variously as “link aggregation,” “port trunking,” “port teaming,” and/or “load sharing.” The goal of these techniques is to logically bond the set, N, of forwarding interfaces together to achieve N times as much transmit bandwidth. To achieve this, each packet that the networking equipment forwards is mapped to one of the set, N, of forwarding interfaces in a uniform manner (i.e., no one of the set, N, of forwarding interfaces can be systematically preferred over another).
One way to provide load balancing over the paths and/or forwarding interfaces while maintaining ordering constraints of dataflows is to assign packets of a dataflow to one of the multiple paths or forwarding interfaces based on results of “hash function” operations or, simply, “flow hashing”. Flow hashing maps an input “key” formed from salient features of the dataflow (commonly referred to as “flow identifiers”) to an output hash digest having fewer bits. The hash digest is then mapped to one of the paths or forwarding interfaces between 0 and N−1.
Hash functions for performing flow hashing are generally characterized by uniformity, implementation area, and computation time. Uniformity can be assessed by comparison to a random assignment. That is, if two randomly selected keys differ, then there should be a 50% probability that their hash digests will be different. Cyclic Redundancy Check (“CRC”) is the hash function generally recognized as being suitable for high-performance, high-integration hardware implementations. The CRC and like-type hash functions, when evaluated over real-world network packets, however, may exhibit severe non-uniformity. The non-uniformity arises because real-world keys are not distributed in a uniform, random manner. Commonly, the flow identifiers contained in the keys, e.g., MAC or IP addresses, are sequential in nature.